SHA-2
SHA-2 (англ. Secure Hash Algorithm Version 2 — безопасный алгоритм хеширования, версия 2) — собирательное название однонаправленных хеш-функций SHA-224, SHA-256, SHA-384 и SHA-512. Хеш-функции предназначены для создания «отпечатков» или «дайджестов» сообщений произвольной битовой длины. Применяются в различных приложениях или компонентах, связанных с защитой информации. История Хеш-функции SHA-2 разработаны Агенством национальной безопасности США и опубликованы Национальным институтом стандартов и технологий в федеральном стандарте обработки информации FIPS PUB 180-2 в августе 2002 года. В этот стандарт также вошла хеш-функция SHA-1, разработанная в 1995 году. В феврале 2004 года в FIPS PUB 180-2 была добавлена SHA-224 . В октябре 2008 года вышла новая редакция стандарта — FIPS PUB 180-3. В июле 2006 года появился стандарт RFC 4634 «Безопасные хеш-алгоритмы США (SHA и HMAC-SHA)», описывающий SHA-1 и семейство SHA-2. Агентство национальной безопасности от лица государства выпустило патент на SHA-2|US patent 6829355 под лицензией Royalty Free. Алгоритм Общее описание right|thumb|400px|Схема одной итерации алгоритмов SHA-2 Хеш-функции семейства SHA-2 построены на основе . Исходное сообщение после дополнения разбивается на блоки, каждый блок — на 8 слов. Алгоритм пропускает каждый блок сообщения через цикл с 64-мя или 80-ю итерациями (раундами). На каждой итерации 2 слова из восьми преобразуются, функцию преобразования задают остальные слова. Результаты обработки каждого блока складываются, сумма является значением хеш-функции. Подробнее — см. псевдокод. Алгоритм использует следующие битовые операции: * ǁ — Конкатенация, * + — Сложение, * and — Побитовое «И», * or — Побитовое «ИЛИ», * xor — Исключающее «ИЛИ», * shr — Логический сдвиг вправо, * rotr — Циклический сдвиг вправо. В следующей таблице показаны некоторые технические характеристики различных вариантов SHA-2. «Внутреннее состояние» обозначает промежуточную хеш-сумму после обработки очередного блока данных: Псевдокод SHA-256 Пояcнения: Все переменные беззнаковые, имеют размер 32 бита и при вычислениях суммируются по модулю 232 ''message — исходное двоичное сообщение m'' — преобразованное сообщение ''Инициализация переменных (первые 32 бита дробных частей квадратных корней первых восьми простых чисел 2 до 19): h0 := 0x6A09E667 h1 := 0xBB67AE85 h2 := 0x3C6EF372 h3 := 0xA54FF53A h4 := 0x510E527F h5 := 0x9B05688C h6 := 0x1F83D9AB h7 := 0x5BE0CD19 Таблица констант (первые 32 бита дробных частей кубических корней первых 64-х простых чисел 2 до 311): k0..63 := 0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5, 0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5, 0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3, 0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174, 0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC, 0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA, 0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7, 0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967, 0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13, 0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85, 0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3, 0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070, 0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5, 0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3, 0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208, 0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2 Предварительная обработка: m := message ǁ [единичный бит] m := m ǁ [k нулевых бит], где k''' — наименьшее неотрицательное число такое, что битовая длина итогового сообщения будет ≡ 448 (mod 512) (сравнима по модулю 512 c 448) m := m ǁ Длина(message) — длина исходного сообщения в битах в виде 64-битного числа с порядком байтов от старшего к младшему Далее сообщения обрабатывается последовательными порциями по 512 бит: разбить сообщение на куски по 512 бит '''для каждого куска разбить кусок на 16 слов длиной 32 бита: w0..15 Сгенерировать дополнительные 48 слов: для i от 16 до 63 s0 := (wi-15 rotr 7) xor (wi-15 rotr 18) xor (wi-15 shr 3) s1 := (wi-2 rotr 17) xor (wi-2 rotr 19) xor (wi-2 shr 10) wi := wi-16 +''' s0 '''+ wi-7 +''' s1 Инициализация вспомогательных переменных: a := h0 b := h1 c := h2 d := h3 e := h4 f := h5 g := h6 h := h7 Основной цикл: '''для i от 0 до 63 Σ0 := (a rotr 2) xor (a rotr 13) xor (a rotr 22) Ma := (a and b) xor (a and c) xor (b and c) t2 := Σ0 + Ma Σ1 := (e rotr 6) xor (e rotr 11) xor (e rotr 25) Ch := (e and f) xor ((not e) and g) t1 := h + Σ1 + Ch + ki + wi h := g g := f f := e e := d + t1 d := c c := b b := a a := t1 + t2 Добавить полученные значения к ранее вычисленному результату: h0 := h0 + a h1 := h1 + b h2 := h2 + c h3 := h3 + d h4 := h4 + e h5 := h5 + f h6 := h6 + g h7 := h7 + h Получить итоговое значения хеша: digest = hash = h0 ǁ h1 ǁ h2 ǁ h3 ǁ h4 ǁ h5 ǁ h6 ǁ h7 SHA-224 идентичен SHA-256, за исключением: * для инициализации переменных h0—h7 используются другие начальные значения. * в итоговом хеше опускается значение h7. Начальные значения переменных h0—h7 в SHA-224: h0 := 0xC1059ED8 h1 := 0x367CD507 h2 := 0x3070DD17 h3 := 0xF70E5939 h4 := 0xFFC00B31 h5 := 0x68581511 h6 := 0x64F98FA7 h7 := 0xBEFA4FA4 SHA-512 имеет идентичную структуру, но: * слова имеют длину 64 бита. * используется 80 раундов вместо 64. * начальные значения переменных и константы расширены до 64 бит. * в сдвиг в операциях rotr и shr производится на другое число позиций. SHA-384 идентичен SHA-512, за исключением: * переменные h0—h7 имеют другие начальные значения. * в итоговом хеше опускаются значения h6 и h7. Начальные значения переменных h0—h7 в SHA-384 (первые 64 бита дробных частей квадратных корней простых чисел с 9-го по 16-е 23 до 53): h1 := CBBB9D5DC1059ED8 h2 := 629A292A367CD507 h3 := 9159015A3070DD17 h4 := 152FECD8F70E5939 h5 := 67332667FFC00B31 h6 := 8EB44A8768581511 h7 := DB0C2E0D64F98FA7 h8 := 47B5481DBEFA4FA4 Примеры Ниже приведены примеры хешей SHA-2. Для всех сообщений подразумевается использование кодировки ASCII. SHA-224("The quick brown fox jumps over the lazy dog") = 730E109B D7A8A32B 1CB9D9A0 9AA2325D 2430587D DBC0C38B AD911525 SHA-256("The quick brown fox jumps over the lazy dog") = D7A8FBB3 07D78094 69CA9ABC B0082E4F 8D5651E4 6D3CDB76 2D02D0BF 37C9E592 SHA-384("The quick brown fox jumps over the lazy dog") = CA737F10 14A48F4C 0B6DD43C B177B0AF D9E51693 67544C49 4011E331 7DBF9A50 9CB1E5DC 1E85A941 BBEE3D7F 2AFBC9B1 SHA-512("The quick brown fox jumps over the lazy dog") = 07E547D9 586F6A73 F73FBAC0 435ED769 51218FB7 D0C8D788 A309D785 436BBB64 2E93A252 A954F239 12547D1E 8A3B5ED6 E1BFD709 7821233F A0538F3D B854FEE6 Малейшее изменение сообщения в подавляющем большинстве случаев приводит к совершенно другому хешу вследствие лавинного эффекта. К примеру, при изменении dog на cog получится: SHA-256("The quick brown fox jumps over the lazy cog") = E4C4D8F3 BF76B692 DE791A17 3E053211 50F7A345 B46484FE 427F6ACC 7ECC81BE Криптоанализ На 2008 год хеш-функции SHA-2, в отличие от SHA-1, недостаточно изучены. В 2003 году Гилберт и Хандшух провели исследование SHA-2, но не нашли каких-либо уязвимостей. Криптоанализ хеш-функции подразумевает исследование устойчивости алгоритма по отношению, по меньшей мере, к следующим видам атак: * нахождение коллизий, т. е. разных сообщений с одинаковым хешем. * нахождение прообраза, т. е. неизвестного сообщения по его хешу. От устойчивости хеш-функции к нахождению коллизий зависит безопасность электронной цифровой подписи с использованием данного хеш-алгоритма. От устойчивости к нахождению прообраза зависит безопасность хранения хешей паролей для целей аутентификации. В марте 2008 года индийские исследователи Сомитра Кумар Санадия и Палаш Саркар опубликовали найденные ими коллизии для 22 итераций SHA-256 и SHA-512.Somitra Kumar Sanadhya, Palash Sarkar. 22-Step Collisions for SHA-2 В сентябре того же года они представили метод конструирования коллизий для усечённых вариантов SHA-2 (21 итерация).Somitra Kumar Sanadhya, Palash Sarkar. Deterministic Constructions of 21-Step Collisions for the SHA-2 Hash Family Презентация «Deterministic Constructions of 21-Step Collisions for the SHA-2 Hash Family» Ввиду алгоритмической схожести SHA-2 с SHA-1 и наличия у последней потенциальных уязвимостей ведутся поиски улучшенных альтернатив.Schneier on Security: NIST Hash Workshop Liveblogging (5) Hash cracked — heise Security Новый стандарт будет назван SHA-3, он будет определен конкурсом, проводимым Национальным институтом стандартов и технологий в 2008—2012 гг.Tentative Timeline of the Development of New Hash Functions Применение и сертификация См. также Применение хеширования SHA-224, SHA-256, SHA-384 и SHA-512 законом США допускаются к использованию в некоторых правительственных приложениях, включая использование в рамках других криптографических алгоритмов и протоколов, для защиты информации, не имеющей грифа секретности. Стандарт также допускает использование SHA-2 частными и коммерческими организациями.[http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchangenotice.pdf FIPS 180-2: Secure Hash Standard (SHS): 6. Applicability] Хеш-функции SHA-2 используются для проверки целостности данных и в различных криптографических схемах. На 2008 год семейство хеш-функций SHA-2 не имеет такого широкого распространения, как MD5 и SHA-1SHA-1, SHA-256 в результатах поисковой системы Google, несмотря на обнаруженные у последних недостатки. Некоторые примеры применения SHA-2 указаны в таблице: Как показали исследованияSpeed Comparison of Popular Crypto Algorithms http://www.cryptopp.com/benchmarks.html , алгоритмы SHA-2 работают в 2—3 раза медленнее других популярных хеш-алгоритмов MD5, SHA-1, Tiger и RIPEMD-160. Сертификация Реализации SHA-2, как и всех Федеральных стандартов обработки информации, могут быть сертифицированы для использования в некоторых приложениях на территории США. Сертификация происходит в рамках процедуры Cryptographic Module Validation Program , которая проводится Национальным институтом стандартов и технологий США совместно с канадским Бюро безопасности связи. На 5 ноября 2008 года было сертифицировано более 250-ти реализаций SHA-2, четыре из которых могли оперировать сообщениями с длиной в битах некратной восьми.SHS Validation List Примечания Литература * * См. также * MD5 * SHA-1 * Коллизия * Федеральные стандарты обработки информации * Хеширование Внешние ссылки * Онлайн калькулятор различных типов хешей * Febooti fileTweak Hash & CRC — программа для вычисления различных (MD5, SHA-1, SHA-2 и др.) хешей файлов Стандарты * FIPS 180-3: Secure Hash Standard (SHS) * RFC 3874: A 224-bit One-way Hash Function: SHA-224 * RFC 4634: US Secure Hash Algorithms (SHA and HMAC-SHA) Реализации * The OpenSSL Project — широко используемая библиотека OpenSSL crypto включает свободные реализации SHA-224, SHA-256, SHA-384 и SHA-512 * Crypto++ Library — свободная реализация криптографических алгоритмов на C++ * Bouncy Castle Library — свободная библиотека Java и C# классов, которая включает реализации SHA-224, SHA-256, SHA-384 и SHA-512, а также других хеш-алгоритмов Whirlpool, Tiger, RIPEMD, ГОСТ Р 34.11-94, MD2, MD4 и MD5 * jsSHA — свободная библиотека Javascript, включающая полное семейство хеш-функций SHA-2 Криптоанализ * Последние достижения в криптоанализе SHA-256/224 * Анализ усечённого варианта SHA-256 * Коллизии усечённого варианта SHA-256 * Нелинейные атаки на усечённые варианты хеш-функций SHA-2 * Детерминированное конструирование коллизий для семейства хешей SHA-2 с 21 итерацией Категория:Криптографические хеш-функции cs:Secure Hash Algorithm da:SHA de:Secure Hash Algorithm en:SHA es:SHA fi:SHA fr:SHA-1 ko:SHA hr:SHA-2 he:SHA it:Secure Hash Algorithm ja:SHA lt:SHA nl:SHA-familie pl:SHA-1 pt:SHA1 sk:Secure Hash Algorithm sr:SHA vi:SHA zh:SHA 家族